'''
 * @desc : ID3算法构建决策树
 * @auth : TYF
 * @date : 2019/8/26 - 23:05

 (1)期望 : 试验中每次可能结果的概率乘以其结果的总和，反映了随机变量随机取值的大小
 (2)信息量 : 度量信息的不确定性
    信息熵 : 度量信息的不确定性的期望，即信息量的平均值
 (3)如何判断信息量 : 越不确定的事件信息量越大(如天阳从东边升起这个确定发生的事件信息量为0)
 (4)决策树的构建 : 信息增益  Y信息熵  条件Y下结果X的信息熵
                  IG(Y|X) = H(Y) - H(Y|X)
                 找出当前数据集中哪个特征对划分数据分类时起到决定性作用
                 对于单个特征，系统在有该特征的参与下和无该特征参与下，系统信息量的差值就是该特征的信息增益，
                 也就是该特征对整个系统的信息量贡献。因为一个特征的信息增益越大，表明这个特征使得系统由不确定变为确定的能力越强。
'''



from math import log

#样本示例
'''
序列  天气     温度     湿度   是否有风   是否打球
1    sunny     hot     high    FALSE     no 
2    sunny     hot     high    TRUE      no 
3    overcast  hot     high    FALSE     yes 
4    rainy     mild    high    FALSE     yes 
5    rainy     cool    normal  FALSE     yes 
6    rainy     cool    normal  TRUE      no 
7    overcast  cool    normal  TRUE      yes 
8    sunny     mild    high    FALSE     no 
9    sunny     cool    normal  FALSE     yes 
10   rainy     mild    normal  FALSE     yes 
11   sunny     mild    normal  TRUE      yes 
12   overcast  mild    high    TRUE      yes 
13   overcast  hot     normal  FALSE     yes 
14   rainy     mild    high    TRUE      no
'''

def createDataSet():
    dataSet = [
        ['sunny',   'hot', 'high',  'FALSE', 'no'],
        ['sunny',   'hot', 'high',  'TRUE',  'no'],
        ['overcast','hot', 'high',  'FALSE', 'yes'],
        ['rainy',   'mild','high',  'FALSE', 'yes'],
        ['rainy',   'cool','normal','FALSE', 'yes'],
        ['rainy',   'cool','high',  'FALSE',  'no'],
        ['overcast','cool','normal','TRUE',  'yes'],
        ['sunny',   'mild','high',  'FALSE', 'no'],
        ['sunny',   'cool','normal','FALSE', 'yes'],
        ['rainy',   'mild','normal','FALSE', 'yes'],
        ['sunny',   'mild','normal','TRUE',  'yes'],
        ['overcast','mild','high',  'TRUE',  'yes'],
        ['overcast','hot', 'normal','FALSE', 'yes'],
        ['rainy',   'mild','high',  'TRUE',  'no']
    ]
    labels = ['天气','温度','湿度','是否有风']
    return dataSet,labels

dataSet,labels = createDataSet()

#计算给定数据集香农熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) #样本个数
    labelCounts = {}
    for featVec in dataSet: #样本示例 sunny/hot/high/FALSE/no
        currentLabel = featVec[-1] #最后一列是标签
        if currentLabel not in labelCounts.keys(): #为所有标签可能取值创建字典  标签:标签出现次数
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries  #计算每个类别的概率
        shannonEnt -= prob*log(prob,2) #p*log(p)再求和
    return shannonEnt #返回数据集信息熵(信息量的平均值) 即H(x)

#样本集信息熵
#shannonEnt = calcShannonEnt(dataSet)
#print('shannonEnt:',shannonEnt)

"""
splitDataSet(通过遍历dataSet数据集，求出index对应的colnum列的值为value的行)
就是依据index列进行分类，如果index列的数据等于 value的时候，就要将 index 划分到我们创建的新的数据集中
Args:
    dataSet 数据集                 待划分的数据集
    index 表示每一行的index列        划分数据集的特征
    value 表示index列对应的value值   需要返回的特征的值。
Returns:
    index列为value的数据集【该数据集需要排除index列】
"""
def splitDataSet(dataSet, index, value):
    retDataSet = []
    for featVec in dataSet:
        # index列为value的数据集【该数据集需要排除index列】
        # 判断index列的值是否为value
        if featVec[index] == value:
            # chop out index used for splitting
            # [:index]表示前index行，即若 index 为2，就是取 featVec 的前 index 行
            reducedFeatVec = featVec[:index]
            '''
            请百度查询一下： extend和append的区别
            music_media.append(object) 向列表中添加一个对象object
            music_media.extend(sequence) 把一个序列seq的内容添加到列表中 (跟 += 在list运用类似， music_media += sequence)
            1、使用append的时候，是将object看作一个对象，整体打包添加到music_media对象中。
            2、使用extend的时候，是将sequence看作一个序列，将这个序列和music_media序列合并，并放在其后面。
            music_media = []
            music_media.extend([1,2,3])
            print music_media
            #结果：
            #[1, 2, 3]
            music_media.append([4,5,6])
            print music_media
            #结果：
            #[1, 2, 3, [4, 5, 6]]
            music_media.extend([7,8,9])
            print music_media
            #结果：
            #[1, 2, 3, [4, 5, 6], 7, 8, 9]
            '''
            reducedFeatVec.extend(featVec[index + 1:])
            # [index+1:]表示从跳过 index 的 index+1行，取接下来的数据
            # 收集结果值 index列为value的行【该行需要排除index列】
            retDataSet.append(reducedFeatVec)
    return retDataSet

#获取第0列值为2的样本,并将这些样本第一列去掉,得到的就是按照第0列的属性进行划分的样本
#retDataSet = splitDataSet(dataSet,0,2)
#print('dataSet:',dataSet)
#print('retDataSet:',retDataSet)



"""
chooseBestFeatureToSplit(选择最好的特征)
    Args:
        dataSet 数据集
    Returns:
        bestFeature 最优的特征列
"""
def chooseBestFeatureToSplit(dataSet):
    # 最后一列是label
    numFeatures = len(dataSet[0]) - 1
    # 数据集的原始信息熵
    baseEntropy = calcShannonEnt(dataSet)
    # 初始化最优信息增益,及其Featurn编号
    bestInfoGain, bestFeature = 0.0, -1
    # 遍历所有样本
    for i in range(numFeatures):
        # 获取对应feature下的所有值
        featList = [example[i] for example in dataSet]
        # 使用set对list数据进行去重
        uniqueVals = set(featList)
        # 初始化子集信息熵
        newEntropy = 0.0
        # 对所有属性进行一次数据集划分,得到去掉该熟悉的一个子集
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # 对该子集计算概率
            prob = len(subDataSet)/float(len(dataSet))
            # 对该子集计算信息熵
            newEntropy += prob * calcShannonEnt(subDataSet)
        # 计算信息增益,在有/无该特征时信息熵的变化大小来评估该特征对样本集的信息贡献
        infoGain = baseEntropy - newEntropy
        print('infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy)
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    print('bestFeature:',bestFeature)
    return bestFeature

#第一个最优属性的选择
#bestFeature = chooseBestFeatureToSplit(dataSet)
#print('bestFeature:',bestFeature)




'''
创建决策树
'''
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
    # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改
    # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
    del(labels[bestFeat])
    # 取出最优列，然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print 'myTree', value, myTree
    return myTree


#构建决策树
tree = createTree(dataSet,labels)
print('tree:',tree)


#测试
def classify(inputTree, featLabels, testVec):
    """classify(给输入的节点，进行分类)

    Args:
        inputTree  决策树模型
        featLabels Feature标签对应的名称
        testVec    测试输入的数据
    Returns:
        classLabel 分类的结果值，需要映射label才能知道名称
    """
    # 获取tree的根节点对于的key值
    firstStr = inputTree.keys()[0]
    # 通过key得到根节点对应的value
    secondDict = inputTree[firstStr]
    # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
    featIndex = featLabels.index(firstStr)
    # 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    print ('+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat)
    # 判断分枝是否结束: 判断valueOfFeat是否是dict类型
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else:
        classLabel = valueOfFeat
    return classLabel


'''
{'湿度':{
	'high':{
		'天气':{
			'overcast':'yes', 
			'rainy':{
				'温度':{
					'mild':{
							'是否有风':{'
								TRUE':'no',
								'FALSE':'yes'}},
					'cool':'no'}},
				'sunny':'no'}},
	'normal':'yes'
}}
'''